﻿// 0828train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <deque>

using namespace std;

/*
如果两个人相遇，则 pk，体力值大的能够打赢体力值小的，体力值相同则同归于尽，
赢的人才能继续往前逃生，并减少相应的体力

输入描述
系列非 0 整数，用空格隔开，正数代表向右逃生，负数代表向左逃生
输出描述
最终能够逃生的人构成的序列

输入
5 10 8 -8 -5
输出
5 5

8 与 -8 相遇，同归于尽，10 遇到-5，打赢并减少五点体力，最终逃生的为[5，5]，均从右侧港口逃生

输入
5 6 -10
输出
1

 */
class Solution01
{
public:
    Solution01(vector<int>&num_vec)
    {
        int vec_size = num_vec.size();
        vector<int>stack_vec;

        //>0直接入栈 往右
        //<0 如果栈顶<0，入栈
        //栈顶>0 弹出
        //比较大小，while(栈顶<curr), abs(curr)-abs(top)

        for (int i=0; i<vec_size; i++)
        {
            int curr = num_vec[i];
            if (curr > 0)
            {
                stack_vec.push_back(curr);
                continue;
            }

            //<0的情况
            while (!stack_vec.empty() && stack_vec.back()>0 && abs(curr)>0)
            {
                if (abs(stack_vec.back()) >= abs(curr))
                {
                    //非空 && abs(栈顶)>abs(当前)
                    int top_node = stack_vec.back();
                    stack_vec.pop_back();
                    int diff = abs(top_node) - abs(curr);
                    curr = diff;
                    break;
                }
                
                int top_node = stack_vec.back();
                stack_vec.pop_back();
                int diff = abs(curr) - abs(top_node);
                curr = diff*(-1); //负数取胜了
                
            }

            if (abs(curr)>0) stack_vec.push_back(curr);
            //for---
        }

        for (auto&num:stack_vec)
        {
            cout << num << ' ';
        }

        //Solution01
    }
};


/*
n1 = n2，则 n1、n2全部出栈，压入新数据 m (m = 2*n1)
n1 = n2 + ... + ny( y的范围为[3,x]) ，则 n1, n2, ..., ny 全部出栈，压入新数据 m (m = 2*n1)。
如果上述规则都不满足，则不做操作

如：依次向栈压入 6、1、2、3，当压入 2 时，栈顶至栈底依次为 [2,1,6]；
当压入 3 时，3 = 2 + 1，3、2、1 全部出栈，重新入栈整数6，
此时栈顶至栈底依次为 [6,6]；6 = 6，两个 6 全部出栈，压入 12，最终栈中只剩个元素 12。
向栈中输入一串数字，请输出应用此规则后栈中最终存留的数字。

输入
10 20 50 80 1 1
输出
2 160
 */

class Solution02
{
public:
    void handleSum()
    {
        int st_sum = 0;
        int count = 0;
        
        for (int i = stack_v.size() - 1; i >= 0; i--)
        {
            st_sum += stack_v[i];
            count += 1;
            if (st_sum == curr)
            {
                is_find = true;
                break;
            }
            if (st_sum > curr) break;
        }

        if (is_find)
        {
            while (count--)
            {
                stack_v.pop_back();
            }
            curr = st_sum + curr;
        }
    }
    Solution02(vector<int>&num_vec)
    {
        for (int i=0; i<num_vec.size();i++)
        {
            curr = num_vec[i];
            while (!stack_v.empty() && stack_v.back()<=curr)
            {
                if (!stack_v.empty() && stack_v.back() == curr)
                {
                    stack_v.pop_back();
                    curr = curr * 2;
                }

                if (!stack_v.empty() && stack_v.back() < curr)
                {
                    is_find = false;
                    handleSum();
                    if (!is_find) break;
                }
            }
            stack_v.push_back(curr);
        }

        for (int i=stack_v.size()-1; i>=0; i--)
        {
            int num = stack_v[i];
            cout << num << ' ';
        }
        //Solution02
    }
private:
    bool is_find = false;
    int curr = 0;
    vector<int>stack_v;
};


/*
 按照员工的工号顺序，每个人随机抽取一个数字
 按照工号的顺序往后排列，第一个 大的，
 获得“距离*数字差值”的奖金
 如果遇不到比自己数字大的，就给自己分配随机数数量的奖金

例如，按照工号顺序的随机数字是：2,10,3
那么第2个员工的数字10比第1个员工的数字2大
所以，第1个员工可以获得1*(10-2)=8
第2个员工后面没有比他数字更大的员工，所以，他获得他分配的随机数数量的奖金，就是10
第3个员工是最后一个员工，后面也没有比他更大数字的员工，所以他得到的奖金是3
请帮老板计算一下每位员工最终分到的奖金都是多少钱。

输入描述
第一行n表示员工数量
第二是每位员工分配的随机数字

输出描述
最终每位员工分到的奖金数量

输入
3
2 10 3
输出
8 10 3

 */
class Solution03
{
public:
    vector<int>result;
    Solution03(vector<int>&num_vec)
    {
        //index
        vector<int>stack_v;

        result.resize(num_vec.size());

        //top<curr, 弹出
        for (int i=num_vec.size()-1; i>=0; i--)
        {
            //距离*数字差值
            while (!stack_v.empty()&&num_vec[stack_v.back()] <= num_vec[i])
            {
	            //栈顶<=curr弹出
                stack_v.pop_back();
            }

            if (!stack_v.empty())
            {
	            //栈顶存在
                int diff = num_vec[stack_v.back()] - num_vec[i];
                int distance = stack_v.back() - i;
                result[i] = distance * diff;
            }
            else
            {
                result[i] = num_vec[i];
            }
            stack_v.push_back(i);
            //for------
        }

        for (auto&num:result)
        {
            cout << num << ' ';
        }

        //Solution03
    }
};

int main()
{
	{
        int vec_size;
        cin >> vec_size;
        vector<int>num_vec(vec_size);

        for (int i=0; i<vec_size; i++)
        {
            cin >> num_vec[i];
        }

        //int vec_size = 3;
        //string input = "2 10 3";
        //stringstream oh_sstream(input);
        //string token;
        //vector<int>num_vec;
        //while (oh_sstream>>token)
        //{
        //    num_vec.push_back(stoi(token));
        //}

        Solution03 solu(num_vec);

        return 0;
	}
	{
        vector<int>num_vec;
        //string input = "10 20 50 80 1 1";
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (oh_sstream>>token)
        {
            num_vec.push_back(stoi(token));
        }

        Solution02 solu(num_vec);

        return 0;
	}
    //5 10 8 -8 -5
    vector<int>num_vec;
    //string input = "5 6 -10";
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    while (oh_sstream>>token)
    {
        num_vec.push_back(stoi(token));
    }
    Solution01 solu(num_vec);
    
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
